package 二叉树高频题目_上_不含树型dp;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 二叉树的锯齿形层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
public class Code02_ZigzagLevelOrderTraversal {

    // 定义树节点
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    // 提交以下的方法
    // 用每次处理一层的优化bfs就非常容易实现
    // 如果测试数据量变大了就修改这个值
    public static int MAXN = 2001;
    public TreeNode[] queue = new TreeNode[MAXN];
    public int l, r;
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root != null){
            l = r = 0;
            queue[r++] = root;
            // false 代表从左往右
            // true 代表从右往左
            boolean reverse = false;
            while(l < r){
                int size = r - l;
                // reverse == false, 左 -> 右， l....r-1, 收集size个
                // reverse == true,  右 -> 左， r-1....l, 收集size个
                // 左 -> 右, i = i + 1
                // 右 -> 左, i = i - 1
                // 首先将这一层的节点按照从左往右 或者 从右往左 进行链表收集
                ArrayList<Integer> list = new ArrayList<>();
                for(int i = reverse ? r-1 : l, j = reverse ? -1 : 1, k = 0; k < size; k++, i = i + j ){
                    list.add(queue[i].val);
                }
                //然后再进行这一层的遍历，弹出节点，队列加入子节点
                for(int i = 0; i < size; i++){
                    TreeNode cur = queue[l++];
                    if(cur.left != null){
                        queue[r++] = cur.left;
                    }
                    if(cur.right != null){
                        queue[r++] = cur.right;
                    }
                }
                ans.add(list);
                // 每隔一层进行一次反转
                reverse = !reverse;
            }
        }
        return ans;
    }
}
